package leetcode101.search_problem.dfs;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code6
 * @Description 79. Word Search
 * Given an m x n grid of characters board and a string word, return true if word exists in the grid.
 * <p>
 * The word can be constructed from letters of sequentially adjacent cells,
 * where adjacent cells are horizontally or vertically neighboring.
 * The same letter cell may not be used more than once.
 * <p>
 * 示例:
 * <p>
 * board =
 * [
 * ['A','B','C','E'],
 * ['S','F','C','S'],
 * ['A','D','E','E']
 * ]
 * <p>
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-02 10:08
 */
public class Code6 {

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        String word1 = "ABCCED";
        String word2 = "SEE";
        String word3 = "ABCB";
        System.out.println(exist(board, word1));
        System.out.println(exist(board, word2));
        System.out.println(exist(board, word3));
    }

    public static boolean flag;

    public static boolean exist(char[][] board, String word) {
        flag = false;
        boolean[][] check = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfs(board, check, i, j, 0, word);
            }
        }
        return flag;
    }

    public static void dfs(char[][] board, boolean[][] check, int i, int j, int pos, String word) {
        if (i < 0 || i > board.length - 1 || j < 0 || j > board[i].length - 1) {
            return;
        }
        if (pos == word.length() - 1 && board[i][j] == word.charAt(pos) && !check[i][j]) {
            flag = true;
            return;
        }
        if (board[i][j] != word.charAt(pos)) {
            return;
        }
        if (check[i][j]) {
            return;
        }
        if (pos != word.length() - 1) {
            check[i][j] = true;
            dfs(board, check, i + 1, j, pos + 1, word);
            dfs(board, check, i - 1, j, pos + 1, word);
            dfs(board, check, i, j + 1, pos + 1, word);
            dfs(board, check, i, j - 1, pos + 1, word);
            check[i][j] = false;
        }
    }
}
